package com.dmall.play.interview.chapter07;

public class Leetcode235 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "TreeNode {" +
                    "val=" + val +
                    '}';
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p == q) {
            return p;
        }
        if (p.val < root.val && root.val < q.val) {
            // p 在 root 的左边，q 在 root 的右边，直接返回 root
            return root;
        } else if (p.val > root.val && root.val > q.val) {
            // p 在 root 的右边，q 在 root 的左边，直接返回 root
            return root;
        }
        if (root.val == p.val || root.val == q.val) {
            // p 或者 q 的值等于 root 的值，直接返回 root
            return root;
        }
        // 其他情况就一定是 p 和 q 都在 root 的同一边
        if (root.val > q.val) {
            // 都在 root 的左边
            return lowestCommonAncestor(root.left, p, q);
        } else {
            // 都在 root 的右边
            return lowestCommonAncestor(root.right, p, q);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        Leetcode235 leetcode235 = new Leetcode235();
        TreeNode treeNode = leetcode235.lowestCommonAncestor(root, root, root.right);
        System.out.println(treeNode.val);
    }
}
